package com.yiguang.algorithm.backtracking;

import com.alibaba.fastjson.JSON;
/*
 [
 [1,1,1,1,1],
 [1,0,0,0,1],
 [1,0,1,0,1],
 [1,0,0,0,1],
 [1,1,1,1,1]
 ]
 */
public class Test {
	public static void main(String[] args) {
		int[][] arr = {{1,2,3,4,5},{16,17,18,19,6},{15,24,25,20,7},{14,23,22,21,8},{13,12,11,10,9}};
		Test test1 = new Test();
		System.out.println(test1.getMaxLength(arr));
		
		
	}
	
/*  动态规划之记忆化搜索
	链接：https://www.nowcoder.com/questionTerminal/7205912f04974f099714d8a49f78609d
	来源：牛客网
	
	NowCoder喜欢滑雪，因为滑雪的确很刺激。为了获得速度，必须从高处往低处滑。现在知道某片区域的海拔，如下所示
	1  2  3  4 5
	16 17 18 19 6
	15 24 25 20 7
	14 23 22 21 8
	13 12 11 10 9
	可以从某个点滑向上下左右四个方向中海拔比当前位置低的点。例如上图中一条可行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1是最长的一条。
	现在给出区域的海拔，你能帮忙计算最长的滑道有多长吗？
 */
	public int getMaxLength(int[][] arr) {
		int column = arr.length;
		int row = arr[0].length;
		int[][] status = new int[column][row];
		int max = 0;
		for(int i=0; i<column; i++) {
			for(int j=0; j<row; j++) {
				recursion(i, j, arr, status);
				if(status[i][j]>max) {
					max = status[i][j];
				}
			}
		}
		return max;
	}
	
	private int recursion(int i, int j, int[][] arr, int[][] status) {
		int column = arr.length;
		int row = arr[0].length;
		if(status[i][j]!=0) {
			return status[i][j];
		}
		int max = 0;
		if(i-1>=0 && arr[i][j]>arr[i-1][j]) {
			int current = recursion(i-1, j, arr, status);
			if(current>max) {
				max = current;
			}
		}
		if(j+1<row && arr[i][j]>arr[i][j+1]) {
			int current = recursion(i, j+1, arr, status);
			if(current>max) {
				max = current;
			}
		}
		if(i+1<row && arr[i][j]>arr[i+1][j]) {
			int current = recursion(i+1, j, arr, status);
			if(current>max) {
				max = current;
			}
		}
		if(j-1>=0 && arr[i][j]>arr[i][j-1]) {
			int current = recursion(i, j-1, arr, status);
			if(current>max) {
				max = current;
			}
		}
		status[i][j] = max+1;
		return status[i][j];
	}


}
